//find the maximum subarray(e.g. the subarray with the max sum) using divide & conquer method
#include <iostream>

using std::cout;
using std::endl;

class LHS {
public:
	int low;
	int high;
	int sum;
	
	bool operator=(LHS &a) {
		this->low = a.low;
		this->high = a.high;
		this->sum = a.sum;
	}
};

LHS max_cross(int *a,int left,int mid,int right) {
	LHS ans; 
	int max_left = -100;
	int sum_left = 0;
	int i_left = mid;
	for(int i=mid;i>=left;i--) {
		sum_left += a[i];
		if(sum_left > max_left) {
			max_left = sum_left;
			i_left = i;
		}
	}
	ans.low = i_left;
	
	int max_right = -100;
	int sum_right = 0;
	int i_right = mid+1;
	for(int j=mid+1;j<=right;j++) {
		sum_right += a[j];
		if(sum_right>max_right) {
			max_right = sum_right;
			i_right = j;
		}
	}
	ans.high = i_right;

	ans.sum = max_left + max_right;
	
	return ans;
}

LHS max_suba (int *a,int left,int right) {
	LHS ans;
	if(left == right) {
		ans.low = left;
		ans.high = right;
		ans.sum = a[left];
		return ans;
	}
	int mid = (left+right)/2;
	LHS ans_c = max_cross(a,left,mid,right);
	LHS ans_l = max_suba(a,left,mid);
	LHS ans_r = max_suba(a,mid+1,right);
	
	
	
	if(ans_l.sum>=ans_r.sum && ans_l.sum>=ans_c.sum) {
		ans.low = ans_l.low;
		ans.high = ans_l.high;
		ans.sum = ans_l.sum;
	}
	else if(ans_r.sum>=ans_l.sum && ans_r.sum>=ans_c.sum) {
		ans.low = ans_r.low;
		ans.high = ans_r.high;
		ans.sum = ans_r.sum;
	}
	else {
		ans.low = ans_c.low;
		ans.high = ans_c.high;
		ans.sum = ans_c.sum;
	}
	return ans;
}

int main() {
	int a[16] = {13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};
	LHS ans = max_suba(a,0,15);
	cout << "max sum= " << ans.sum <<endl;
	cout << "low= " << ans.low << endl;
	cout << "high=" << ans.high << endl;
	return 0;
}